import java.util.*;

public class Topology {
    public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int[][] a = new int[][]{{1, 2}, {3, 4}};
        for (int[] ints : a) {
            System.out.println(ints);
        }
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        Integer[] array = list.toArray(new Integer[0]);

        int[] arr = new int[array.length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = array[i];
        }

        System.out.println(array.length);

        String s = "aa";
        for(char c : s.toCharArray()){}

    }

    /**
     * 火星词典 diff
     */
    public String alienOrder(String[] words) {
        Map<Character, Integer> in = new HashMap<>();
        Map<Character, Set<Character>> map = new HashMap<>();

        // 初始化和建图
        for(String s : words){
            for(char c : s.toCharArray()){
                in.put(c, 0);
            }
        }

        for(int i = 0; i < words.length; i++){
            for(int j = i + 1; j < words.length; j++){
                String a = words[i];
                String b = words[j];
                for(int k = 0; k < a.length(); ){
                    char ca = a.charAt(k);
                    char cb = b.charAt(k);
                    if(ca != cb){
                        if(!map.containsKey(ca)){
                            map.put(ca, new HashSet());
                        }
                        if(!map.get(ca).contains(cb)){
                            map.get(ca).add(cb);
                            in.put(cb, in.get(cb) + 1);
                        }
                        break;
                    }
                    k++;
                    // ab abc
                    if(k == b.length() && k < a.length()) return "";
                }
            }
        }

        //过去到入度为0的
        Queue<Character> queue = new LinkedList<>();
        for(char c : in.keySet()){
            if(in.get(c) == 0) queue.add(c);
        }

        StringBuilder ret = new StringBuilder();
        while(!queue.isEmpty()){
            char poll = queue.poll();
            for(char c : map.getOrDefault(poll, new HashSet<>())){
                int v = in.get(c) - 1;
                in.put(c, v);;
                if(v == 0) queue.add(c);
            }
            ret.append(poll);
        }

        if(ret.length() != in.size()) return "";
        return ret.toString();
    }

    /**
     * 课程表II
     */
    public int[] findOrder(int n, int[][] p) {
        int[] in = new int[n];
        //建表
        Map<Integer, List<Integer>> map = new HashMap<>();

        for(int[] i : p){
            int a = i[0]; int b = i[1];
            if(!map.containsKey(b)){
                //不存在边的点也给他放进去了
                map.put(b, new LinkedList<>());
            }
            map.get(b).add(a);
            in[a]++;
        }

        //找到入度为0的点
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < in.length; i++){
            if(in[i] == 0) queue.add(i);
        }

        //拓扑排序
        int[] ret = new int[n];
        int index = 0;
        while(!queue.isEmpty()){
            int poi = queue.poll();
            //出掉入度为0 的并且减去指向点的入度
            for(int i : map.getOrDefault(poi, new LinkedList<>())){
                in[i]--;
                if(in[i] == 0) queue.add(i);
            }
            ret[index++] = poi;
        }
        return index == n ? ret : new int[0];
    }
    /**
     * 课程表
     * 建图 看是否有循环
     * 拓扑排序可以看是否有循环
     */
    public boolean canFinish(int n, int[][] p) {
        int[] in = new int[n];

        //起点 和 指向的点
        Map<Integer, List<Integer>> map = new HashMap<>();
        //建图
        for (int i = 0; i < p.length; i++) {
            int[] dir = p[i];
            int s = dir[1];
            int e = dir[0];
            // dir[1] -> dir[0]

            in[e]++;
            if (!map.containsKey(s)) {
                map.put(s, new LinkedList<>());
            }
            List l = map.get(s);
            l.add(e);
        }

        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (in[i] == 0) queue.add(i);
        }

        int ret = 0;
        while (!queue.isEmpty()) {
            int poll = queue.poll();
            List<Integer> l = map.getOrDefault(poll, new LinkedList<>());
            for (int i : l) {
                in[i]--;
                if (in[i] == 0) queue.add(i);
            }
            ret++;
        }
        return ret == n;
    }
}

